interface Queue<T> {
  enqueue(element: T, priority: number): void;
  dequeue(): T | undefined;
}

class PriorityQueue<T> implements Queue<T> {
  private items: { element: T; priority: number }[] = [];

  constructor() {
    this.items = [];
  } 

  enqueue(element: T, priority: number) {
    this.items.push({ element, priority });
    this.sort();
  }

  dequeue() {
    return this.items.shift()?.element;
  }

  private sort() {
    this.items.sort((a, b) => a.priority - b.priority);
  }
}

class PriorityHeap<T> implements Queue<T> {
  private items: { element: T; priority: number }[] = [];

  constructor() {
    this.items = [];
  }

  enqueue(element: T, priority: number) {
    this.items.push({ element, priority });
    this.heapUp(this.items.length - 1);
  }

  dequeue() {
    const root = this.items[0];
    const end = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = end!;
      this.heapDown(0);
    }
    return root?.element;
  }

  private heapUp(index: number) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (index > 0 && this.items[index].priority > this.items[parentIndex].priority) {
      [this.items[index], this.items[parentIndex]] = [this.items[parentIndex], this.items[index]];
      this.heapUp(parentIndex);
    }
  }

  private heapDown(index: number) {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let largestIndex = index;
    if (leftChildIndex < this.items.length && this.items[leftChildIndex].priority > this.items[largestIndex].priority) {
      largestIndex = leftChildIndex;
    }
    if (rightChildIndex < this.items.length && this.items[rightChildIndex].priority > this.items[largestIndex].priority) {
      largestIndex = rightChildIndex;
    }
    if (largestIndex !== index) {
      [this.items[index], this.items[largestIndex]] = [this.items[largestIndex], this.items[index]];
      this.heapDown(largestIndex);
    }
  }
}

const h = new PriorityHeap<string>();
h.enqueue("Task 1", 2);
h.enqueue("Task 2", 1);
h.enqueue("Task 3", 3);
console.log(h.dequeue());
console.log(h.dequeue());